1. Field of the Invention
The invention relates to communications, specifically the routing and filtering of packets within digital communications networks.
2. Description of the Related Art
On a packet-switched network such as the Internet, traffic between a source and a destination is in the form of one or more discrete units, or datagrams. The creation of datagrams is typically performed by a number of software protocols working in coordination. These protocols are typically visualized as a vertical stack of layers. Each layer/protocol accepts a datagram from an adjacent layer/protocol, performs a specific set of one or more tasks on that datagram, and then delivers the resulting datagram to the next layer/protocol in the stack.
FIG. 1 is a graphical depiction of the five-layer protocol stack of the Internet, how the protocols in the stack format datagrams, how those protocol layers correspond to objects in the real world, and how datagrams are routed from source to destination via the Internet.
By convention, protocol layers are numbered from bottom to top, with physical layer 102 being first, datalink layer 104 second, network layer 106 third, transport layer 108 fourth, and application layer 110 fifth and last.
In operation, data to be transmitted from a source 112 to a destination 150 first travels through protocol layers 110-102 from the top down at source 112. Data originates at the source application layer. For example, source web-server software application 114 running on web-server computer 126 generates Hypertext Transfer Protocol (HTTP) application data 116 destined for destination 150, in this case, web-browser software application 160 running on laptop computer 156.
Web-server application software 114 hands application data 116 to transport layer 108, in this example, a Terminal Control Protocol (TCP) layer. The TCP layer's responsibility is to (1) determine whether application data 112 is accurately transmitted from source 112 to destination 150 and (2) initiate a resend if it is not. Since there may be multiple pieces of application software running on both source and destination, TCP layer 108 distinguishes different applications by using specified TCP port numbers, e.g., source port 118 and destination port 158. At source 112, TCP layer 108 treats application data 116 (in this case, HTTP data) as TCP payload 122 and encapsulates that payload 122 by prepending a TCP header 120 that contains, inter alia, TCP source port number 118 and TCP destination port number 158. In general, for a particular protocol layer, the term “payload” refers to that portion of a datagram that is not part of the datagram header or footer (if present). Thus, the payload of one layer will include the payload, header, and footer (if present) of the next higher layer in the protocol stack.
TCP hands resulting TCP datagram 124 to network layer 106, in this example, an Internet Protocol (IP) layer. The IP layer's task is to route IP datagrams from one network address to another. IP layer 106 treats TCP datagram 124 as IP payload 130 and encapsulates that payload by prepending an IP header 128, which contains, inter alia, source and destination IP addresses. The result is IP datagram 132.
Next, IP layer 106 hands IP datagram 132 to datalink layer 104, the layer charged with moving data from one hardware device to another. In this example, the datalink protocol is Ethernet, and the Ethernet device is an Ethernet card 134 within web-server computer 126. Datalink layer 104 treats IP datagram 132 as Ethernet payload 138 and encapsulates that payload by prepending Ethernet header 136 and appending Ethernet footer 140. Datalink layer 104 then sends resulting Ethernet datagram 142 to the Internet 146 over physical layer 102, in this example, a copper cable 144 conforming to the 10BaseT physical-layer specification.
Connecting source 112 and destination 150 is the Internet 146. The Internet 146 can be visualized as a collection of interconnected routing applications (routers) 148. Routers 148 independently route each datagram from source to destination based, in part, on information located within the datagram. As part of the routing process, routers may make modifications to the datagrams.
Once Ethernet datagram 142 has transited the Internet 146, it ascends through the protocol stack at destination 150 in reverse order, shedding headers and footers (de-encapsulation) until original application data 116 is presented to destination application 160. In particular, Ethernet cable 152 delivers Ethernet datagram 142 to datalink (Ethernet) device 154. Ethernet device 154 removes Ethernet header 136 and Ethernet footer 140 and hands IP datagram 132 to network (IP) layer 106. Network (IP) layer 106 removes IP header 128 and delivers TCP datagram 124 to transport (TCP) layer 108. Lastly, transport (TCP) layer 108 discards TCP header 120 and delivers application data 116 to application 160.
FIG. 2 is an exploded view of datagram 132 of FIG. 1 and illustrates the results of IP packet fragmentation. Each of IP header 128 and TCP header 120 comprises a number of fields. Source TCP Port field 220 identifies source port 118, which is used to route responses back to source application 114. Destination TCP Port field 222 identifies destination port 158, which is used to route application data 116 to application software 160 on destination computer 156.
IP header 128 comprises, among other fields, Total Length field 208, which indicates the size in bytes of IP datagram 132. Source IP Address field 202 and Destination IP Address field 204 contain the IP addresses of source and destination devices 126 and 156, respectively.
During the course of routing IP datagrams, it is occasionally necessary to break such datagrams into a sequence of smaller IP datagrams, for example, to meet the constraints of an intermediate network or router in the transmission path. This operation is called IP packet fragmentation. An unfragmented IP datagram is called a packet, and each smaller IP datagram that results from breaking up a packet is called a fragment. As referred to herein, the offset order of a set of fragments belonging to a single packet is the order in which those fragments occurred in that packet.
Each fragment possesses a complete IP header, but, typically, only offset-0 fragment 246 (i.e., the first fragment of a fragmented packet) possesses TCP header 120 from original packet 132. The opposite of IP fragmentation is reassembly, that is, the reconstitution of a packet from its constituent fragments.
An important characteristic of a packet-switched network, such as the Internet, is that each router routes a particular datagram along what that router has determined is the optimal transmission path at that particular point in time. As a consequence, the transmission path taken by a datagram transmitted by a particular source for a particular destination may differ from the transmission paths taken by other datagrams transmitted by the same source for the same destination at different points in time. Thus, it is possible for a source to transmit datagrams in a particular sequence, e.g., offset order, to a destination, and for those same datagrams to arrive at the destination in a different sequence, referred to herein as the received sequence. Furthermore, a destination may receive fragments for a particular packet interleaved with datagrams corresponding to other packets. Yet further, one or more fragments might never arrive at their destinations at all.
Thus, a destination needs to determine (1) which fragments belong to which packets, (2) whether or not all fragments for a particular packet have been received, and (3) the offset order of a set of fragments belonging to a particular packet. This information is found in Identification field 206, Fragment Offset field 210, and More Fragments field 212 of IP header 128.
Identification field 206 is set to a value (e.g., 216, for this example) that is unique for that source-destination pair for the time the packet will be active on the Internet. All fragments of a particular packet will inherit the Identification value of the packet.
Fragment Offset field (FO) field 210 indicates the offset of this fragment relative to the beginning of the data portion of the IP payload in units of eight bytes. In other words, a fragment's fragment offset value indicates where in the data portion of the original packet the payload of this fragment occurred. Thus, fragment offset values can be used to resequence out-of-offset-order received fragments into their proper offset order. According to RFC 791, the Internet Protocol specification, the offset for an unfragmented packet must be 0. The offset for the first fragment of a fragmented packet (referred to herein as the offset-0 fragment) is also 0.
More Fragments field (MF) 212, a 1-bit true/false field, indicates whether or not this datagram is followed (in offset order) by another datagram having the same Identification value. RFC 791 specifies an MF value of 0 (false) for a packet and for the last offset fragment of a packet. For all fragments but the last offset fragment of a packet, RFC 791 specifies an MF value of 1 (true).
If, for example, IP packet 132 (having a total length of 324 bytes and an IP header length of 20 bytes) must transit a network with an Maximum Transmission Unit (MTU) of 148 bytes, then IP packet 132 may be broken up into three fragments: 246, 266, and 286, each of which is an IP datagram in its own right. Specifically, the 304 bytes of IP data 124 (including TCP header 120) will be broken up into three pieces (120 and 244, 264, and 284) of 128 bytes, 128 bytes, and 48 bytes, respectively. Each piece will then be prepended with its own IP header (230, 250, 270), which, for the purposes of this illustration, is assumed to be 20 bytes long, yielding fragments 246 (148 bytes), 266 (148 bytes), and 286 (68 bytes).
Some of the fields in fragment headers 230, 250, and 270 will be identical to the corresponding fields in packet IP header 128. Specifically, Source IP Address (202, 232, 252, 272), Destination IP Address (204, 234, 254, 274), and Identification (206, 236, 256, 276) will be identical.
Other fields in fragment headers 230, 250, and 270 will differ from the corresponding fields in packet IP header 128. Total Length fields 238, 258, and 278 will change to reflect the effects of fragmentation. Similarly, Fragment Offset fields 240, 260, and 280 will now reflect the fragments' offset order, in 8-byte blocks. Lastly, More Fragments fields 242, 262, and 282 now indicate that (1) fragmentation has occurred and (2) that fragment 286 is the last offset fragment.
Fragmentation complicates datagram routing. Routers routinely require data that is not duplicated from fragment to fragment, e.g., TCP header information. Consequently, a router may receive a fragment that it will be unable to route utilizing solely the information contained within that fragment. Furthermore, some routing operations require a router to modify packet data (e.g., Network Address Translation), and thus a router may need to modify one or more fragments of a packet. However, fragmentation complicates more than just datagram routing.
In addition to the efficient routing of IP datagrams, a second concern of many who use the Internet today is network security. Routinely, datagrams are manipulated and purposefully introduced onto the Internet to disrupt communications or to gain unauthorized access to protected devices and protected network services. Such “attacks” come in many different forms. One example is the denial-of-service attack, where a router or other device is deliberately flooded with datagrams in order to compromise or even prevent legitimate communications. Another example is the spoofing attack, where IP and TCP headers are manipulated to make it appear that one or more datagrams are coming from a trusted or authorized source, giving the sender unauthorized access.
Thus, there will often be an element in the transmission path, e.g., a firewall or intrusion-detection system (IDS), whose function is to detect and/or prevent such attacks. Typically, a firewall or IDS evaluates a received datagram against one or more rules. If a received datagram satisfies the one or more rules, it is passed (processed for re-transmission); otherwise, it is dropped (discarded). This selective passing and dropping of datagrams in accordance with rules is known as filtering.
Filtering typically involves zones, stateful inspection, and application-layer filtering. A zone is a range of allowable source IP addresses for a particular interface. There can be multiple zones defined for a single interface. If the source IP address of a datagram received on an interface does not fall within any of the zones defined for that interface, then the datagram is dropped. Thus, for example, if an interface has two zones, a first that allows all datagrams with a source IP address of 192.168.1.1 to 192.167.1.127, and a second that allows all datagrams with a source IP address beginning with 204, then datagram with a source IP address of 19.63.8.30 received on that interface will be dropped.
Stateful inspection examines not only datagrams in isolation, but also the ongoing state of communications between source and destination, and thus the relationship between the instant datagram and related datagrams, if any, that preceded it. For example, a firewall performing stateful inspection may drop inbound datagrams that are not responses to communications initiated from behind the firewall. Application-layer filtering, also known as deep packet inspection, goes beyond datagram headers and inspects application-layer data in order to make a pass/drop decision.
Just as with datagram routing, fragmentation complicates the task of datagram filtering. When an IP packet has been fragmented, the data required by a rule may be located in any one or more of the packet's fragments. Furthermore, some fragment sequences themselves pose threats against network elements, even when the contents of those individual fragments appear innocuous. Such sequences may be accidental or intentionally crafted by an attacker intent upon probing, damaging, or intruding into a targeted network. For example, certain sequences of overlapping fragments can be used to bypass some firewall filters and gain access to protected services. Similarly, out-of-offset-order fragment sequences can be designed to bypass firewalls or overwhelm them in a denial-of-service attack.
Routers, firewalls, and intrusion-detection systems adopt different strategies for filtering and routing fragments. Simpler strategies include passing all fragments, dropping all fragments, dropping all out-of-offset-order fragments, or tracking and dropping all overlapping and/or duplicate fragment sequences. Passing all fragments shifts the processing of fragments to a downstream device, such as a protected host, and defeats the purpose of a firewall, which is to block certain communications from reaching critical resources. Dropping all fragments is effective against fragmentation attacks, but also quashes many legitimate communications. Dropping all out-of-offset-order fragments is similarly overinclusive and does not protect against overlapping fragment attacks. Furthermore, none of these strategies provides for more-sophisticated filtering of fragments or for the modification of fragments.
A more-effective strategy for fragment filtering and routing is full reassembly. Here, a router buffers in memory all fragments for a particular packet, re-sequences any out-of-offset-order fragments into their offset order, and reassembles those fragments to yield an intact packet. The router then filters/routes the intact packet, re-fragments the packet if appropriate, and re-transmits the resulting datagram(s) towards the appropriate destination.
One disadvantage of full reassembly is that it is resource-intensive, requiring a router to buffer every fragment of a packet in memory for as long as it takes for all fragments of that packet to arrive. Furthermore, the acts of buffering, re-sequencing, and reassembling consume processing resources.
Another shortcoming of full reassembly is visibility. Since full reassembly re-transmits either a complete packet or a set of fragments in offset order, there is often a difference between the datagrams entering and exiting full reassembly. Someone monitoring such data streams can determine that there is a firewall in operation and can begin attacking that firewall.
An alternative to full reassembly is to route fragments based on the information contained in the offset-0 fragment (fragment-0 routing). Such a method is detailed in U.S. Pat. No. 6,795,866, the teachings of which are hereby incorporated by reference in their entirety. This method buffers in memory only those fragments (if any) that arrive before the offset-0 fragment. If and when the offset-0 fragment arrives, the method makes a routing decision based on the IP and TCP headers of the offset-0 fragment and re-transmits that fragment accordingly. The method then applies that routing decision to any buffered fragments and any subsequently received fragments. Thus, with the exception of the offset-0 fragment, which is typically routed first, fragments are routed by this method in the order in which they were received.
Fragment-0 routing possesses several advantages over full reassembly. Fragment-0 routing does not require buffering all fragments, but only those that arrive before the offset-0 fragment, thus often consuming fewer memory resources than full reassembly. Furthermore, fragment-0 routing is, on average, quicker than full reassembly because buffered fragments do not sit idle awaiting the arrival of the slowest fragment, but only until the offset-0 fragment arrives. Lastly, the steps of re-sequencing and reassembling a complete packet have been eliminated, reducing overhead and increasing efficiency.
Yet, fragment-0 routing also suffers from several drawbacks. First, the method does not provide the ability to make a routing decision based on information outside the offset-0 fragment, e.g., application-layer data. Second, the method does not provide for the detection or mitigation of a wide range of fragment-based attacks. In other words, fragment-0 routing does not perform filtering. Third, the method does not provide full control over the re-transmission of fragments. For example, a system administrator may want to re-transmit fragments as a fully reassembled packet, and not individually in the received order.
The first of these shortcomings (examining fragments other than the fragment-0 fragment) was considered in U.S. Pat. No. 7,065,086, the teachings of which are hereby incorporated by reference in their entirety. This method alludes to the examination of other fragments in addition to fragment 0, but provides no details on how such examination would take place. As with fragment-0 routing, this method does not perform filtering, nor does it provide full control over the re-transmission of fragments.